package com.dyz.leetcode._15_BFSAndDFS;

public class _200_numIslands {
    int n,m;
    public int numIslands(char[][] grid){
        n = grid.length;
        m = grid[0].length;
        int res=0;
        for (int i=0; i<n;i++){
            for(int j=0; j<m; j++){
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    private void dfs(char[][] grid, int i, int j) {
        if(i<0||i>=n||j<0||j>=m||grid[i][j]=='0'){return;}
        grid[i][j]='0';
        dfs(grid, i-1, j);
        dfs(grid,i, j-1);
        dfs(grid, i+1, j);
        dfs(grid, i, j+1);
    }

    private char[][] grid;
    private int rows;
    private int cols;
    private boolean[][] visited;
    private int[][] dirs = {{-1, 0},{1, 0},{0, -1},{0, 1}}; //左边 右边 上边 下边
    public int numIslands1(char[][] grid){
        this.grid = grid;
        this.rows = grid.length;
        this.cols = grid[0].length;
        this.visited = new boolean[rows][cols];
        int ans=0;
        for(int row=0; row<rows; row++){
            for(int col=0; col<cols; col++){
                if(grid[row][col]=='1' && !visited[row][col]){
                    dfs1(row, col);
                    ans++;
                }
            }
        }
        return ans;

    }

    private void dfs1(int row, int col) {
        if(!isArea(row,col) || grid[row][col]=='0' || visited[row][col]){
            return;
        }
        visited[row][col]=true;
        //  遍历上下左右
        for (int[] dir:dirs){
            int nextRow = row + dir[0];
            int nextCol = col+dir[1];
            dfs1(nextRow, nextCol);
        }
    }

    private boolean isArea(int row, int col){
        return row >= 0 && row < rows && col >= 0 && col < cols;
    }
}
